﻿#include "data.hpp"
#include "zzj.col.hpp"
#include<stack>
#include<queue>
using namespace std;
using namespace col;
namespace maze
{
	inline pair<Path, int32_t> Map::calcPath(std::size_t start, std::size_t end) const
	{
		Path path;
		int32_t min_score = numeric_limits<int32_t>::max();

		// 将线性索引转换为二维坐标
		auto start_loc = make_pair(static_cast<int>(start / m_width), static_cast<int>(start % m_width));
		auto end_loc = make_pair(static_cast<int>(end / m_width), static_cast<int>(end % m_width));

		// 检查起点和终点是否有效
		if (start_loc.first < 0 || start_loc.first >= static_cast<int>(m_height) || start_loc.second < 0 || start_loc.second >= static_cast<int>(m_width) ||
			end_loc.first < 0 || end_loc.first >= static_cast<int>(m_height) || end_loc.second < 0 || end_loc.second >= static_cast<int>(m_width)) {
			cout << "起点和终点不得越界" << endl;
			cout << "该迷宫范围在 1~" << m_width * m_height  << endl;
			return { path,min_score };
		}

		// 检查起点和终点是否为道路
		if (m_map[start_loc.first][start_loc.second].attr == Attr::WALL) {
			cout << "起点不为空" << endl;
			return { path,min_score };
		}
		if (m_map[end_loc.first][end_loc.second].attr == Attr::WALL) {
			cout << "终点不为空" << endl;
			return { path,min_score };
		}

		// 记录访问状态的二维数组
		vector<vector<bool>> visited(m_height, vector<bool>(m_width, false));
		// 存储路径的优先队列（最小堆）
		priority_queue<pair<int32_t, Locate>, vector<pair<int32_t, Locate>>, greater<pair<int32_t, Locate>>> path_pq;
		// 父节点记录，用于重建路径
		vector<vector<Locate>> parent(m_height, vector<Locate>(m_width, { -1, -1 }));
		// 分数记录
		vector<vector<int32_t>> scores(m_height, vector<int32_t>(m_width, numeric_limits<int32_t>::max()));

		// 从起点开始
		path_pq.push({ 0, start_loc });
		visited[start_loc.first][start_loc.second] = true;
		scores[start_loc.first][start_loc.second] = 0;

		// 方向数组，表示上下左右四个方向
		vector<Locate> directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

		bool found = false;

		while (!path_pq.empty()) {
			auto current_pair = path_pq.top();
			path_pq.pop();
			int32_t current_score = current_pair.first;
			Locate current = current_pair.second;

			// 如果当前点是终点，标记为找到路径
			if (current.first == end_loc.first && current.second == end_loc.second) {
				found = true;
				min_score = current_score;
				break;
			}

			// 如果当前路径的得分大于已记录的得分，跳过
			if (current_score > scores[current.first][current.second]) {
				continue;
			}

			// 按照上下左右的顺序遍历相邻节点
			for (const auto& dir : directions) {
				int nx = current.first + dir.first;
				int ny = current.second + dir.second;

				// 检查是否越界，是否可走（非墙壁）
				if (nx >= 0 && nx < static_cast<int>(m_height) && ny >= 0 && ny < static_cast<int>(m_width) &&
					m_map[nx][ny].attr != Attr::WALL) {
					// 计算新分数
					int32_t new_score = current_score;
					switch (m_map[nx][ny].attr) {
					case Attr::ROAD:
						new_score += 2;
						break;
					case Attr::TREASURE:
						new_score += 1;
						break;
					case Attr::TRAP:
						new_score += 3;
						break;
					}

					// 如果新分数小于记录的分数，更新分数并添加到优先队列
					if (new_score < scores[nx][ny]) {
						scores[nx][ny] = new_score;
						parent[nx][ny] = current;
						path_pq.push({ new_score, { nx, ny } });
					}
				}
			}
		}

		if (found) {
			// 重建路径
			//map.displayPathGraph(path);
			Path path;
			Locate current = end_loc;
			while (current != start_loc) {
				path.push_back(current);
				current = parent[current.first][current.second];
			}
			path.push_back(start_loc); // 明确添加起点
			reverse(path.begin(), path.end());
			return { path,min_score };
		}
		else {
			cout << "未找到路径" << endl;
			return { path,min_score };
		}
	}

	inline bool Map::displayPath(Path& path) const
	{

		cout << "Path:" << endl;
		for (const auto& loc : path)
		{
			cout << "(" << loc.first+1 << ", " << loc.second+1 << ") ";
		}
		cout << endl;
		return true;
	}

	inline bool Map::displayPathGraph(Path& path) const
	{
		constexpr int wide{ 3 };
		// 打印列号
		auto col = Color(CName::CYAN);
		cout << "L\\C";
		for (size_t j = 1; j <= m_width; ++j) {
			printf("%3zu ", j);
		}
		cout << endl;

		// 打印矩阵和行号
		for (size_t i = 1; i <= m_height; ++i) {
			// 打印行号
			auto row_col = Color(CName::GREEN);
			printf("%3zu ", i);

			for (size_t j = 0; j < m_width; ++j) {
				bool is_path = false;
				for (const auto& loc : path) {
					if (loc.first == static_cast<int>(i-1) && loc.second == static_cast<int>(j)) {
						is_path = true;
						break;
					}
				}

				if (is_path) {
					// 路径上的点用*表示
					col.setPrn(CName::WHITE);
					printf("%3s ", "*");
				}
				else {
					switch (m_map[i-1][j].attr) {
					case Attr::ROAD:
						col.setPrn(CName::WHITE);
						printf("%3s ", "路");
						break;
					case Attr::WALL:
						col.setPrn(CName::YELLOW);
						printf("%3s ", "墙");
						break;
					case Attr::TRAP:
						col.setPrn(CName::RED);
						printf("%3s ", "陷");
						break;
					case Attr::TREASURE:
						col.setPrn(CName::BLUE);
						printf("%3s ", "宝");
						break;
					default:
						printf("%3s ", "？");
					}
				}
			}
			cout << endl;
		}
		return true;
	}
}

